package wjl.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * twoSum：https://leetcode-cn.com/problems/two-sum/
 * 
 * @author wjl
 *
 */
public class TwoSum {
    public static void main( String[] args ) {
        int[] nums   = {3, 2, 3};
        int   target = 6;
        int[] result = twoSum4( nums, target );
        for ( int i : result ){
            System.out.print( i + " " );
        }
    }

    /*
      暴力解法
      执行结果： 通过 显示详情 执行用时： 83 ms , 
      在所有 Java 提交中击败了 17.75% 的用户 
      内存消耗： 38.9 MB , 在所有 Java 提交中击败了 84.15%的用户
     */
    public static int[] twoSum1( int[] nums, int target ) {
        int[] indexs = {};
        if ( nums == null || nums.length <= 1 ){
            return indexs;
        }
        int     size = nums.length;
        boolean b    = false;
        for ( int i = 0; i < size; i++ ){
            for ( int j = i + 1; j < size; j++ ){
                if ( nums[i] + nums[j] == target ){
                    indexs = new int[] {i, j};
                    b = true;
                    break;
                }
            }
            if ( b ){
                break;
            }
        }
        return indexs;
    }

    /*
     * 奇偶法
     * 执行用时：9 ms, 在所有 Java 提交中击败了49.98%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了69.71%的用户
     */
    public static int[] twoSum2( int[] nums, int target ) {
        int[] indexs = {};
        if ( nums == null || nums.length <= 1 ){
            return indexs;
        }
        int           size     = nums.length;
        List<Integer> jiIndexs = new ArrayList<>();
        List<Integer> ouIndexs = new ArrayList<>();
        for ( int i = 0; i < size; i++ ){
            if ( nums[i] % 2 == 0 ){
                ouIndexs.add( i );
            } else{
                jiIndexs.add( i );
            }
        }
        // 判断target的奇偶性
        if ( target % 2 == 0 ){
            boolean b = false;
            if ( ouIndexs.size() > 1 ){
                for ( int i = 0; i < ouIndexs.size(); i++ ){
                    for ( int j = i + 1; j < ouIndexs.size(); j++ ){
                        if ( nums[ouIndexs.get( i )] + nums[ouIndexs.get( j )] == target ){
                            indexs = new int[] {ouIndexs.get( i ), ouIndexs.get( j )};
                            b = true;
                            break;
                        }
                    }
                    if ( b ){
                        break;
                    }
                }
            }
            if ( jiIndexs.size() > 1 && !b ){
                for ( int i = 0; i < jiIndexs.size(); i++ ){
                    for ( int j = i + 1; j < jiIndexs.size(); j++ ){
                        if ( nums[jiIndexs.get( i )] + nums[jiIndexs.get( j )] == target ){
                            indexs = new int[] {jiIndexs.get( i ), jiIndexs.get( j )};
                            b = true;
                            break;
                        }
                    }
                    if ( b ){
                        break;
                    }
                }
            }
        } else{
            boolean b = false;
            for ( Integer ou : ouIndexs ){
                for ( Integer ji : jiIndexs ){
                    if ( nums[ou] + nums[ji] == target ){
                        indexs = new int[] {ou, ji};
                        b = true;
                        break;
                    }
                }
                if ( b ){
                    break;
                }
            }
        }
        return indexs;
    }

    /*
     * 思路：哈希表存储
     * 执行用时：3 ms, 在所有 Java 提交中击败了73.25%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了88.91%的用户
     */
    public static int[] twoSum3( int[] nums, int target ) {
        int[] indexs = {};
        if ( nums == null || nums.length <= 1 ){
            return indexs;
        }
        int                   size   = nums.length;
        Map<Integer, Integer> numMap = new HashMap<>();
        for ( int i = 0; i < size; i++ ){
            if ( numMap.containsKey( target - nums[i] ) ){
                indexs = new int[] {numMap.get( target - nums[i] ), i};
                break;
            }
            numMap.put( nums[i], i );
        }
        return indexs;
    }

    /*
     * 思路：双指针法
     * 执行用时：3 ms, 在所有 Java 提交中击败了73.11%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了91.69%的用户
     */
    public static int[] twoSum4( int[] nums, int target ) {
        int[] indexs = {};
        if ( nums == null || nums.length <= 1 ){
            return indexs;
        }
        int   size     = nums.length;
        int[] sortNums = Arrays.copyOf( nums, size );
        Arrays.sort( sortNums );
        int i = 0;
        int j = size - 1;
        while (i < j){
            if ( sortNums[i] + sortNums[j] < target ){
                i++;
            } else if ( sortNums[i] + sortNums[j] > target ){
                j--;
            } else{
                break;
            }
        }
        int xNum = sortNums[i];
        int yNum = sortNums[j];
        int x    = -1;
        int y    = -1;
        for ( int k = 0; k < size; k++ ){
            if ( nums[k] == xNum && x == -1 ){
                x = k;
            } else if ( nums[k] == yNum && y == -1 ){
                y = k;
            }
            if ( x != -1 && y != -1 ){
                break;
            }
        }
        indexs = new int[] {x, y};
        return indexs;
    }
}

